{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add Two Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addTwoNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数相加"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <strong>非空</strong> 的链表，表示两个非负的整数。它们每位数字都是按照 <strong>逆序</strong> 的方式存储的，并且每个节点只能存储 <strong>一位</strong> 数字。</p>\n",
    "\n",
    "<p>请你将两个数相加，并以相同形式返回一个表示和的链表。</p>\n",
    "\n",
    "<p>你可以假设除了数字 0 之外，这两个数都不会以 0 开头。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/02/addtwonumber1.jpg\" style=\"width: 483px; height: 342px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [2,4,3], l2 = [5,6,4]\n",
    "<strong>输出：</strong>[7,0,8]\n",
    "<strong>解释：</strong>342 + 465 = 807.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [0], l2 = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]\n",
    "<strong>输出：</strong>[8,9,9,9,0,0,0,1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个链表中的节点数在范围 <code>[1, 100]</code> 内</li>\n",
    "\t<li><code>0 <= Node.val <= 9</code></li>\n",
    "\t<li>题目数据保证列表表示的数字不含前导零</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-two-numbers](https://leetcode.cn/problems/add-two-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-two-numbers](https://leetcode.cn/problems/add-two-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,3]\\n[5,6,4]', '[0]\\n[0]', '[9,9,9,9,9,9,9]\\n[9,9,9,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dummy = ListNode()  # 哨兵节点\n",
    "        carry = 0  # 进位\n",
    "        while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代\n",
    "            if l1: carry += l1.val  # 节点值和进位加在一起\n",
    "            if l2: carry += l2.val  # 节点值和进位加在一起\n",
    "            cur.next = ListNode(carry % 10)  # 每个节点保存一个数位\n",
    "            carry //= 10  # 新的进位\n",
    "            cur = cur.next  # 下一个节点\n",
    "            if l1: l1 = l1.next  # 下一个节点\n",
    "            if l2: l2 = l2.next  # 下一个节点\n",
    "        return dummy.next  # 哨兵节点的下一个节点就是头节点\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)  # l1 和 l2 反转后，就变成【2. 两数相加】了\n",
    "        l3 = self.addTwo(l1, l2)\n",
    "        return self.reverseList(l3)  # 计算完毕后再反转\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse_list(head):\n",
    "            if head.next==None:\n",
    "                return head\n",
    "            current=head\n",
    "            parent= None\n",
    "            while(current is not None):\n",
    "                temp=current.next\n",
    "                current.next=parent\n",
    "                parent=current\n",
    "                current=temp\n",
    "            return parent\n",
    "\n",
    "        l1_rev=reverse_list(l1)\n",
    "        l2_rev=reverse_list(l2)\n",
    "        carry=0\n",
    "        res_head=ListNode()\n",
    "        res_current=res_head\n",
    "        l1_current=l1_rev\n",
    "        l2_current=l2_rev\n",
    "\n",
    "        while l1_current is not None or l2_current is not None or carry!=0:\n",
    "            if l1_current is not None:\n",
    "                l1_num=l1_current.val\n",
    "                l1_current=l1_current.next\n",
    "            else:\n",
    "                l1_num=0\n",
    "            if l2_current is not None:\n",
    "                l2_num=l2_current.val\n",
    "                l2_current=l2_current.next\n",
    "            else:\n",
    "                l2_num=0                \n",
    "            res_current.val=(l1_num+l2_num+carry)%10\n",
    "            carry= int((l1_num+l2_num+carry)/10)\n",
    "            if l1_current is not None or l2_current is not None or carry!=0:\n",
    "                res_current.next=ListNode()\n",
    "                res_current=res_current.next\n",
    "            else:\n",
    "                tail=res_current\n",
    "        res_head = reverse_list(res_head)\n",
    "        return res_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "# 使用栈时间复杂度，空间复杂度都为0(m+n)\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0 \n",
    "        sum = 0\n",
    "        node = None\n",
    "        pre = None\n",
    "        while stack1 or stack2:\n",
    "            if not stack1:\n",
    "                val1 = 0\n",
    "                node = stack2[-1]\n",
    "            else:\n",
    "                node = stack1.pop()\n",
    "                val1 = node.val\n",
    "\n",
    "            if not stack2:\n",
    "                val2 = 0\n",
    "            else:\n",
    "                val2 = stack2.pop().val\n",
    "\n",
    "            sum = (val1 + val2 + carry)%10\n",
    "            carry = (val1 + val2 + carry)//10\n",
    "\n",
    "            node.val = sum\n",
    "            node.next = pre\n",
    "            pre = node\n",
    "        \n",
    "        if carry!=0:\n",
    "            node = ListNode()\n",
    "            node.val = 1\n",
    "            node.next = pre\n",
    "\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        listA = list()\n",
    "        listB = list()\n",
    "        while l1:\n",
    "            listA.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            listB.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        ans_list = list()\n",
    "        sum_up = 0\n",
    "        while listA or listB:\n",
    "            a = 0 if not listA else listA.pop()\n",
    "            b = 0 if not listB else listB.pop()\n",
    "            ans_list.append((a+b+sum_up) % 10)       # sum_up放在里面，防止连续进位\n",
    "            sum_up = (a+b+sum_up) // 10\n",
    "        \n",
    "\n",
    "        if sum_up:\n",
    "            ans_list.append(1)           # 5+5的场景\n",
    "\n",
    "        \n",
    "        ans = ListNode(ans_list.pop())\n",
    "        prev = ans\n",
    "        while ans_list:\n",
    "            prev.next = ListNode(ans_list.pop())   # 需要创建下个节点，创建当前节点的话会多一个next\n",
    "            prev = prev.next\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1,s2=[],[]\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2=l2.next\n",
    "        ans=None\n",
    "        carry=0    \n",
    "        while s1 or s2 or carry!=0:\n",
    "            a=0 if not s1 else s1.pop()\n",
    "            b=0 if not s2 else s2.pop() \n",
    "            cur=a+b+carry\n",
    "            carry=cur//10\n",
    "            cur %=10\n",
    "            curnode=ListNode(cur)\n",
    "            curnode.next=ans\n",
    "            ans=curnode\n",
    "        return ans    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(head):\n",
    "            tail = None\n",
    "            cur = head\n",
    "            while cur is not None:\n",
    "                next = cur.next\n",
    "                cur.next = tail\n",
    "                tail = cur\n",
    "                cur = next\n",
    "            return tail\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        carry = 0\n",
    "        ans = ListNode(0)\n",
    "        cur = ans\n",
    "        while l1 or l2 or carry != 0:\n",
    "            l1v = l1.val if l1 is not None else 0\n",
    "            l2v = l2.val if l2 is not None else 0\n",
    "            s = l1v + l2v + carry\n",
    "            cur.next = ListNode(s % 10)\n",
    "            cur = cur.next\n",
    "            carry = s // 10\n",
    "            if l1 is not None:\n",
    "                l1 = l1.next \n",
    "            if l2 is not None:\n",
    "                l2 = l2.next\n",
    "        return reverse(ans.next)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        dummy = ListNode()\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry:\n",
    "            s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry\n",
    "            carry, val = divmod(s, 10)\n",
    "            dummy.next = ListNode(val, dummy.next)\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reserve(root):\n",
    "            pre = None\n",
    "            while root:\n",
    "                tmp = root.next\n",
    "                root.next = pre\n",
    "                pre = root\n",
    "                root = tmp\n",
    "            return pre\n",
    "        l1 = reserve(l1)\n",
    "        l2 = reserve(l2)\n",
    "        s = ListNode(0)\n",
    "        r = s\n",
    "        flag = 0\n",
    "        while l1 and l2:\n",
    "            cur = l1.val + l2.val + flag\n",
    "            s.next = ListNode(cur%10)\n",
    "            flag = cur//10\n",
    "            s = s.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            cur = l1.val + flag\n",
    "            s.next = ListNode(cur%10)\n",
    "            flag = cur//10\n",
    "            s = s.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            cur = l2.val + flag\n",
    "            s.next = ListNode(cur%10)\n",
    "            flag = cur//10\n",
    "            s = s.next\n",
    "            l2 = l2.next\n",
    "        if flag > 0:\n",
    "            s.next = ListNode(flag)\n",
    "        return reserve(r.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def calc(node):\n",
    "            ans = 0\n",
    "            while node:\n",
    "                ans = ans*10\n",
    "                ans += node.val\n",
    "                node = node.next\n",
    "            return ans\n",
    "        n1 = calc(l1)\n",
    "        n2 = calc(l2)\n",
    "        he = n1+n2\n",
    "        strhe = str(he)\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        for i in range(len(strhe)):\n",
    "            node = ListNode(int(strhe[i]))\n",
    "            p.next = node\n",
    "            p = p.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack_1 = []\n",
    "        stack_2 = []\n",
    "        while l1:\n",
    "            stack_1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack_2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        following = None\n",
    "        carry = 0\n",
    "        while stack_1 or stack_2 or carry != 0:\n",
    "            num_1 = stack_1.pop() if stack_1 else 0\n",
    "            num_2 = stack_2.pop() if stack_2 else 0\n",
    "            temp = (carry + num_1 + num_2) % 10\n",
    "            carry = (carry + num_1 + num_2) // 10\n",
    "            curr = ListNode(temp)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "\n",
    "        return following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack_1 = []\n",
    "        stack_2 = []\n",
    "        while l1:\n",
    "            stack_1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack_2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        following = None\n",
    "        carry = 0\n",
    "        while stack_1 or stack_2 or carry != 0:\n",
    "            num_1 = stack_1.pop() if stack_1 else 0\n",
    "            num_2 = stack_2.pop() if stack_2 else 0\n",
    "            temp = (carry + num_1 + num_2) % 10\n",
    "            carry = (carry + num_1 + num_2) // 10\n",
    "            curr = ListNode(temp)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "        \n",
    "        # if carry:\n",
    "        #     curr = ListNode(carry)\n",
    "        #     curr.next = following\n",
    "        #     following = curr\n",
    "\n",
    "        return following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "    cur, pre = head, None\n",
    "    while cur:\n",
    "      temp = cur.next\n",
    "      cur.next = pre\n",
    "      pre = cur\n",
    "      cur = temp\n",
    "    return pre\n",
    "  def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "    l1, l2 = self.reverseList(l1), self.reverseList(l2)\n",
    "    cur = dummy = ListNode()\n",
    "    carry = 0\n",
    "\n",
    "    while l1 or l2 or carry:\n",
    "      carry += (l1.val if l1 else 0) + (l2.val if l2 else 0) \n",
    "      cur.next = ListNode(carry % 10)\n",
    "      carry //= 10\n",
    "      cur = cur.next\n",
    "      \n",
    "      if l1: l1 = l1.next\n",
    "      if l2: l2 = l2.next\n",
    "\n",
    "    return self.reverseList(dummy.next)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "from typing import Optional\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def get_n(l):\n",
    "            n = 0\n",
    "            while l is not None:\n",
    "                n *= 10\n",
    "                n += l.val\n",
    "                l = l.next\n",
    "            return n\n",
    "        n1 = get_n(l1)\n",
    "        n2 = get_n(l2)\n",
    "\n",
    "        head = ListNode()\n",
    "        cur = head\n",
    "        n = n1 + n2\n",
    "        val_list = [int(c) for c in str(n)]\n",
    "        for v in val_list:\n",
    "            cur.next = ListNode(val = v)\n",
    "            cur = cur.next\n",
    "\n",
    "        return head.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def rever(l: Optional[ListNode]) -> Optional[ListNode]:\n",
    "    head = ListNode(next=l)\n",
    "    cur = l.next\n",
    "    while cur:\n",
    "        l.next = cur.next\n",
    "        cur.next = head.next\n",
    "        head.next = cur\n",
    "        cur = l.next\n",
    "    return head.next\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        \n",
    "        #先全部逆置\n",
    "        #然后从低位到高位进行加和进位\n",
    "        #7 2 4 3\n",
    "        #  5 6 4\n",
    "        #=>\n",
    "        #3 4 2 7\n",
    "        #4 6 5\n",
    "        more = 0\n",
    "        l1 = rever(l=l1)\n",
    "        l2 = rever(l=l2)\n",
    "        res_head = ListNode(next=None)\n",
    "        while l1 and l2:\n",
    "            #head insert\n",
    "            sum = l1.val + l2.val + more\n",
    "            node = ListNode(val=sum % 10, next=res_head.next)\n",
    "            res_head.next = node\n",
    "            if sum >= 10:\n",
    "                more = 1\n",
    "            else:\n",
    "                more = 0\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        if l1:\n",
    "            while l1:\n",
    "                sum = l1.val + more\n",
    "                node = ListNode(val=sum % 10, next=res_head.next)\n",
    "                res_head.next = node\n",
    "                if sum >= 10:\n",
    "                    more = 1\n",
    "                else:\n",
    "                    more = 0\n",
    "                l1 = l1.next\n",
    "            if more == 1:\n",
    "                node = ListNode(val=1, next=res_head.next)\n",
    "                res_head.next = node\n",
    "        elif l2:\n",
    "            while l2:\n",
    "                sum = l2.val + more\n",
    "                node = ListNode(val=sum % 10, next=res_head.next)\n",
    "                res_head.next = node\n",
    "                if sum >= 10:\n",
    "                    more = 1\n",
    "                else:\n",
    "                    more = 0\n",
    "                l2 = l2.next\n",
    "            if more == 1:\n",
    "                node = ListNode(val=1, next=res_head.next)\n",
    "                res_head.next = node\n",
    "        else:\n",
    "            if more == 1:\n",
    "                node = ListNode(val=1, next=res_head.next)\n",
    "                res_head.next = node\n",
    "        return res_head.next\n",
    "        #或者把两个数提出来相加得到结果\n",
    "        #然后转化为链表\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1, n1 = self.reverse(l1)\n",
    "        l2, n2 = self.reverse(l2)\n",
    "        if n1 < n2:\n",
    "            l1, l2 = l2, l1\n",
    "        r = 0\n",
    "        head = l1\n",
    "        while l1:\n",
    "            l2_val = l2.val if l2 else 0\n",
    "            # print(l1.val, /l2_val, r)\n",
    "            l1.val = l1.val + l2_val + r\n",
    "            r = l1.val // 10\n",
    "            l1.val = l1.val % 10\n",
    "            pre = l1\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next if l2 else None\n",
    "        if r > 0:\n",
    "            node = ListNode(r)\n",
    "            pre.next = node\n",
    "        # return head\n",
    "        res, _ = self.reverse(head)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def reverse(self, l):\n",
    "        pre, curr = None, l\n",
    "        n = 0\n",
    "        while curr:\n",
    "            n += 1\n",
    "            nxt = curr.next\n",
    "            curr.next = pre\n",
    "            pre, curr = curr, nxt\n",
    "        return pre, n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self,head:Optional[ListNode])->Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "    def addTwo(self,l1:Optional[ListNode],l2:Optional[ListNode])->Optional[ListNode]:\n",
    "        cur = dummy = ListNode()\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry%10)\n",
    "            carry //= 10\n",
    "            cur = cur.next\n",
    "            if l1:l1 = l1.next\n",
    "            if l2:l2 = l2.next\n",
    "        return dummy.next\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        l3 = self.addTwo(l1,l2)\n",
    "        return self.reverseList(l3)\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    " \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseln(self,head):\n",
    "        cur,pre = head,None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1_n = self.reverseln(l1)\n",
    "        l2_n = self.reverseln(l2)\n",
    "\n",
    "        p1,p2 = l1_n,l2_n\n",
    "        dummy = ListNode()\n",
    "        p = dummy\n",
    "        carry = 0\n",
    "        while p1 or p2 or carry:\n",
    "            val = carry\n",
    "            if p1:\n",
    "                val += p1.val\n",
    "                p1 = p1.next\n",
    "            if p2:\n",
    "                val += p2.val\n",
    "                p2 = p2.next\n",
    "            \n",
    "            carry,val = divmod(val,10)\n",
    "\n",
    "            p.next = ListNode(val)\n",
    "            p = p.next\n",
    "        result_head = dummy.next\n",
    "        return self.reverseln(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def fun(l):\n",
    "            p = None\n",
    "            while l:\n",
    "                l.next, p, l = p, l, l.next\n",
    "            return p\n",
    "\n",
    "        def add(l1, l2):\n",
    "\n",
    "            if not l1: return l2\n",
    "            if not l2: return l1\n",
    "\n",
    "            l1.val += l2.val\n",
    "            if l1.val >= 10:\n",
    "                l1.next = add(ListNode(1), l1.next)\n",
    "                l1.val %= 10\n",
    "\n",
    "            l1.next = add(l1.next, l2.next)\n",
    "            return l1\n",
    "        \n",
    "        l1, l2 = fun(l1), fun(l2) \n",
    "\n",
    "        return fun(add(l1, l2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def lreverse(head):\n",
    "            new = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                node = ListNode(cur.val)\n",
    "                node.next = new\n",
    "                new = node\n",
    "                cur = cur.next\n",
    "            return new\n",
    "        l1 = lreverse(l1)\n",
    "        l2 = lreverse(l2)\n",
    "        ans = None\n",
    "        flag = 0\n",
    "        while l1.val >= 0 or l2.val >= 0 or flag == 1:\n",
    "            t1 = l1.val if l1.val > 0 else 0\n",
    "            t2 = l2.val if l2.val > 0 else 0\n",
    "            if t1 + t2 + flag > 9:\n",
    "                node = ListNode(t1 + t2 + flag - 10)\n",
    "                flag = 1\n",
    "            else:\n",
    "                node = ListNode(t1 + t2 + flag)\n",
    "                flag = 0\n",
    "            node.next = ans\n",
    "            l1 = l1.next if l1.next else ListNode(-1)\n",
    "            l2 = l2.next if l2.next else ListNode(-1)\n",
    "            ans = node\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = self.pushStack(l1)\n",
    "        stack2 = self.pushStack(l2)\n",
    "\n",
    "        dummyHead = ListNode()\n",
    "        head = dummyHead\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry:\n",
    "            val = carry\n",
    "            if stack1:\n",
    "                val += stack1.pop()\n",
    "            if stack2:\n",
    "                val += stack2.pop()\n",
    "            carry = val // 10\n",
    "            tmp = head.next\n",
    "            head.next = ListNode(val % 10)\n",
    "            head.next.next = tmp\n",
    "\n",
    "        return dummyHead.next\n",
    "\n",
    "    def pushStack(self, l: ListNode) -> List[int]:\n",
    "        stack = []\n",
    "        while l:\n",
    "            stack.append(l.val)\n",
    "            l = l.next\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [],[]\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or carry:\n",
    "            s = (s1.pop() if s1 else 0) + (s2.pop() if s2 else 0) + carry\n",
    "            carry, value = divmod(s, 10)\n",
    "            cur = ListNode(val = value)\n",
    "            cur.next = ans\n",
    "            ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        pre = None\n",
    "        while stack1 or stack2 or carry > 0:\n",
    "            sum = 0\n",
    "            sum += 0 if not stack1 else stack1.pop()\n",
    "            sum += 0 if not stack2 else stack2.pop()\n",
    "            sum += carry\n",
    "            carry = sum // 10\n",
    "            cur = ListNode(sum % 10)\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 第1步：将2个链表变成2个字符串\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        \n",
    "        # 第2步：将2个字符串变成数字，相加\n",
    "        str3 = str(eval(''.join([str1, '+', str2])))\n",
    "        # str3 = str(int(str1) + int(str2))\n",
    "        \n",
    "        # 第3步：将结果变成链表\n",
    "        pre = None\n",
    "        for i in range(len(str3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(str3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1, stack2 = [], []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        newListNode = None\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry != 0:\n",
    "            a = 0 if not stack1 else stack1.pop()\n",
    "            b = 0 if not stack2 else stack2.pop()\n",
    "            sum = a + b + carry\n",
    "            carry = sum // 10\n",
    "            sum %= 10\n",
    "            curNode = ListNode(sum, newListNode)\n",
    "            newListNode = curNode\n",
    "        return newListNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        '''翻转链表 -> 计算结果 -> 翻转链表\n",
    "        '''\n",
    "\n",
    "        def reverse_list(head):\n",
    "            '''翻转链表\n",
    "            '''\n",
    "            if head is None or head.next is None:\n",
    "                # 无节点或只有一个节点，直接返回\n",
    "                return head\n",
    "\n",
    "            slow = head; fast = head.next\n",
    "            while(fast is not None):\n",
    "                tmp = fast.next\n",
    "                fast.next = slow\n",
    "                if slow is head:\n",
    "                    slow.next = None\n",
    "                slow = fast\n",
    "                fast = tmp\n",
    "            \n",
    "            return slow\n",
    "\n",
    "        l1 = reverse_list(l1)\n",
    "        l2 = reverse_list(l2)\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        curr_out = dummy_head\n",
    "        curr1 = l1\n",
    "        curr2 = l2\n",
    "        tmp = 0\n",
    "        while(curr1 is not None or curr2 is not None):\n",
    "            val = 0\n",
    "            if curr1 is not None:\n",
    "                val += curr1.val\n",
    "                curr1 = curr1.next\n",
    "\n",
    "            if curr2 is not None:\n",
    "                val += curr2.val\n",
    "                curr2 = curr2.next\n",
    "\n",
    "            val += tmp\n",
    "            curr_out.next = ListNode(val % 10)\n",
    "            curr_out = curr_out.next\n",
    "            tmp = val // 10\n",
    "\n",
    "        if tmp:\n",
    "            curr_out.next = ListNode(tmp)\n",
    "\n",
    "        rst = dummy_head.next\n",
    "        rst = reverse_list(rst)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        rl1, rl2 = self.reverse(l1), self.reverse(l2)\n",
    "        temp = 0\n",
    "        pre = cur = ListNode()\n",
    "        while rl1 or rl2 or temp:\n",
    "            temp += (rl1.val if rl1 else 0) + (rl2.val if rl2 else 0)\n",
    "            cur.next = ListNode(temp%10)\n",
    "            temp //= 10\n",
    "            cur = cur.next\n",
    "            if rl1: rl1 = rl1.next\n",
    "            if rl2: rl2 = rl2.next\n",
    "\n",
    "        return self.reverse(pre.next)\n",
    "    def reverse(self, head):\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        \n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        p0 = new = ListNode(None)\n",
    "        t = 0\n",
    "        while l1 and l2:\n",
    "            a = t + l1.val + l2.val\n",
    "            t, a = divmod(a, 10)\n",
    "            new.next = ListNode(a)\n",
    "            new = new.next\n",
    "            l2 = l2.next\n",
    "            l1 = l1.next\n",
    "        while l1:\n",
    "            a = t + l1.val\n",
    "            t, a = divmod(a, 10)\n",
    "            new.next = ListNode(a)\n",
    "            new = new.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            a = t + l2.val\n",
    "            t, a = divmod(a, 10)\n",
    "            new.next = ListNode(a)\n",
    "            new = new.next\n",
    "            l2 = l2.next\n",
    "        if t!=0:\n",
    "            new.next = ListNode(t)\n",
    "        return self.reverseList(p0.next)\n",
    "\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        dummy = ListNode()\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "\n",
    "        while s1 or s2 or carry:\n",
    "            result_1 = 0 if not s1 else s1.pop()\n",
    "            result_2 = 0 if not s2 else s2.pop() \n",
    "            carry,val = divmod(result_1+result_2+carry, 10)\n",
    "            #carry = (result_1 + result_2 + carry) // 10\n",
    "            #val = (result_1 + result_2 + carry) % 10\n",
    "            dummy.next = ListNode(val, dummy.next)\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num1,num2=0,0\n",
    "        while l1!=None:\n",
    "            num1=num1*10+l1.val\n",
    "            l1=l1.next\n",
    "        while l2!=None:\n",
    "            num2=num2*10+l2.val\n",
    "            l2=l2.next\n",
    "        ret=ListNode()\n",
    "        ret_num=str(num1+num2)\n",
    "        last=ret\n",
    "        for i in ret_num:\n",
    "            q=ListNode(val=int(i))\n",
    "            last.next=q\n",
    "            last=q\n",
    "        return ret.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        nex = None\n",
    "        s = 0\n",
    "        while stack1 or stack2 or s:\n",
    "            n1 = stack1.pop() if stack1 else 0\n",
    "            n2 = stack2.pop() if stack2 else 0\n",
    "            curvalue = n1 + n2 + s\n",
    "            s = curvalue // 10\n",
    "            curvalue %= 10\n",
    "            node = ListNode(val=curvalue, next=nex)\n",
    "            nex = node\n",
    "        return nex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p1 = ListNode(0)\n",
    "        p2 = ListNode(0)\n",
    "        while (l1):\n",
    "            tmp = l1.next\n",
    "            l1.next = p1.next\n",
    "            p1.next = l1\n",
    "            l1 = tmp\n",
    "        while(l2):\n",
    "            tmp = l2.next\n",
    "            l2.next = p2.next\n",
    "            p2.next = l2\n",
    "            l2 = tmp\n",
    "        sum1 = ListNode(0)\n",
    "        cur = sum1\n",
    "        cur1 = p1.next\n",
    "        cur2 = p2.next\n",
    "        flag = 0\n",
    "        while(cur1 and cur2):\n",
    "            sum_ = cur1.val + cur2.val + flag\n",
    "            remainder = sum_ % 10\n",
    "            flag = sum_ // 10\n",
    "            cur.next = ListNode(remainder)\n",
    "            cur = cur.next\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "        while(cur1):\n",
    "            sum_ = cur1.val + flag\n",
    "            remainder = sum_ % 10\n",
    "            flag = sum_ // 10\n",
    "            cur.next = ListNode(remainder)\n",
    "            cur = cur.next\n",
    "            cur1 = cur1.next\n",
    "        while(cur2):\n",
    "            sum_ = cur2.val + flag\n",
    "            remainder = sum_ % 10\n",
    "            flag = sum_ // 10\n",
    "            cur.next = ListNode(remainder)\n",
    "            cur = cur.next\n",
    "            cur2 = cur2.next\n",
    "        if flag != 0:\n",
    "            cur.next = ListNode(flag)\n",
    "        cur = sum1.next\n",
    "        sum1.next = None\n",
    "        while(cur):\n",
    "            tmp = cur.next\n",
    "            cur.next = sum1.next\n",
    "            sum1.next = cur\n",
    "            cur = tmp\n",
    "        return sum1.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        return self.reverseList(self.addTwo(self.reverseList(l1),self.reverseList(l2)))\n",
    "    def reverseList(self,head):\n",
    "        cur=head\n",
    "        prev=None\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=prev\n",
    "            prev=cur\n",
    "            cur=temp\n",
    "        return prev\n",
    "    def addTwo(self,l1,l2):\n",
    "        num_0=0\n",
    "        num_10=0\n",
    "        cur=dum=ListNode()\n",
    "        while l1 or l2:\n",
    "            if not l1:\n",
    "                l1=ListNode(0)\n",
    "            if not l2:\n",
    "                l2=ListNode(0)\n",
    "            num_0=(l1.val+l2.val+num_10)%10\n",
    "            num_10=(l1.val+l2.val+num_10)//10\n",
    "            cur.next=ListNode(val=num_0)\n",
    "            cur=cur.next\n",
    "            l1=l1.next\n",
    "            l2=l2.next\n",
    "        if num_10!=0:\n",
    "            cur.next=ListNode(val=1)\n",
    "        return dum.next\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p1, p2 = l1, l2\n",
    "        s1, s2 = '', ''\n",
    "        while p1:\n",
    "            s1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            s2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        s3 = str(int(s1) + int(s2))\n",
    "        pre = None\n",
    "        for i in range(len(s3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(s3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1=self.reverse(l1)\n",
    "        l2=self.reverse(l2)\n",
    "        l3=self.addTwo(l1,l2)\n",
    "        return self.reverse(l3)\n",
    "    def reverse(self,head:Optional[ListNode])->Optional[ListNode]:\n",
    "        pre=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "          n=cur.next\n",
    "          cur.next=pre\n",
    "          pre=cur\n",
    "          cur=n\n",
    "        return pre\n",
    "    def addTwo(self,l1:Optional[ListNode],l2:Optional[ListNode])->Optional:\n",
    "        dummy=ListNode(0)\n",
    "        cur=dummy\n",
    "        carry=0\n",
    "        while l1 or l2 or carry:\n",
    "            carry+=(l1.val if l1 else 0)+(l2.val if l2 else 0)\n",
    "            cur.next=ListNode(carry%10)\n",
    "            cur=cur.next\n",
    "            carry//=10\n",
    "            if l1:l1=l1.next \n",
    "            if l2:l2=l2.next \n",
    "        return dummy.next\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if l1.val == 0:\n",
    "            return l2\n",
    "        if l2.val == 0:\n",
    "            return l1\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        head = ListNode()\n",
    "        remainder = 0\n",
    "        res = 0\n",
    "        while stack1 and stack2:\n",
    "            num1 = stack1.pop()\n",
    "            num2 = stack2.pop()\n",
    "            res = (num1 + num2 + remainder) % 10\n",
    "            remainder = (num1 + num2 + remainder) // 10\n",
    "            node = ListNode(res)\n",
    "            node.next = head.next\n",
    "            head.next = node\n",
    "        \n",
    "        if len(stack1) != 0:\n",
    "            while stack1:\n",
    "                num = stack1.pop()\n",
    "                res = (num + remainder) % 10\n",
    "                remainder = (num + remainder) // 10\n",
    "                node = ListNode(res)\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "        \n",
    "        if len(stack2) != 0:\n",
    "            while stack2:\n",
    "                num = stack2.pop()\n",
    "                res = (num + remainder) % 10\n",
    "                remainder = (num + remainder) // 10\n",
    "                node = ListNode(res)\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "        \n",
    "        if len(stack1) == 0 and len(stack2) == 0:\n",
    "            if remainder == 0:\n",
    "                return head.next\n",
    "            else:\n",
    "                node = ListNode(remainder)\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "                return head.next\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverse(head=l1)\n",
    "        l2 = self.reverse(head=l2)\n",
    "        cur = dummy = ListNode()\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            if l1: carry += l1.val\n",
    "            if l2: carry += l2.val\n",
    "\n",
    "            cur.next = ListNode(carry%10)\n",
    "            carry //= 10\n",
    "            cur = cur.next\n",
    "\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        return self.reverse(dummy.next)\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "    def reverse(self,head):\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stk1, stk2 = [], []\n",
    "        while l1:\n",
    "            stk1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stk2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        c = 0\n",
    "        a, b = 0, 0\n",
    "        head, f = None, None\n",
    "        while stk1 or stk2:\n",
    "            if stk1:\n",
    "                a = stk1.pop(-1)\n",
    "            if stk2:\n",
    "                b = stk2.pop(-1)\n",
    "            # ans *= 10\n",
    "            f = head\n",
    "            t = ListNode((a+b+c) % 10, f)\n",
    "            head = t\n",
    "            c = (a + b + c) // 10\n",
    "            a = b = 0\n",
    "        if not stk1 and not stk2 and c != 0:\n",
    "            f = head\n",
    "            t = ListNode((a+b+c) % 10, f)\n",
    "            head = t\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        str3 = str(eval(''.join([str1, '+', str2])))\n",
    "        pre = None\n",
    "        for i in range(len(str3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(str3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def addtwo(l1,l2,carry=0):\n",
    "            if not l1 and not l2:\n",
    "                return ListNode(carry) if carry else None\n",
    "            if not l1:\n",
    "                l1,l2 = l2,l1\n",
    "            carry += l1.val + (l2.val if l2 else 0)\n",
    "            l1.val = carry % 10\n",
    "            l1.next = addtwo(l1.next,(l2.next if l2 else None),carry//10)\n",
    "            return l1\n",
    "        def reverse(node):\n",
    "            pre,cur = None,node\n",
    "            while cur:\n",
    "                node_next = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = node_next\n",
    "            return pre\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        l3 = addtwo(l1,l2)\n",
    "        return reverse(l3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num1 = []\n",
    "        num2 = []\n",
    "        while l1:\n",
    "            num1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            num2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        max_n = max(len(num1), len(num2))\n",
    "        if max_n != len(num1):\n",
    "            num1 = [0 for _ in range(max_n-len(num1))] + num1\n",
    "        if max_n != len(num2):\n",
    "            num2 = [0 for _ in range(max_n-len(num2))] + num2\n",
    "\n",
    "        # core\n",
    "        res = []\n",
    "        jin = 0\n",
    "        for i in range(max_n-1, -1, -1):\n",
    "            value = num1[i] + num2[i] + jin\n",
    "            jin = value // 10\n",
    "            cur = value % 10\n",
    "            res.append(cur)\n",
    "        if jin > 0:\n",
    "            res.append(jin)\n",
    "        res = res[::-1]\n",
    "\n",
    "        dump = ListNode()\n",
    "        head = dump\n",
    "        for i in range(len(res)):\n",
    "            tmp = ListNode()\n",
    "            tmp.val = res[i]\n",
    "            head.next = tmp\n",
    "            head = head.next \n",
    "        return dump.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(l):\n",
    "            pre = None\n",
    "            cur = l\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        L1, L2 = [], []\n",
    "        while l1:\n",
    "            L1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            L2.append(l2)\n",
    "            l2 = l2.next\n",
    "\n",
    "        up = 0\n",
    "        head = ListNode()\n",
    "        cur = head\n",
    "        while L1 or L2 or up:\n",
    "            val = up\n",
    "            if L1:\n",
    "                val += L1.pop().val\n",
    "            if L2:\n",
    "                val += L2.pop().val\n",
    "            if val>=10:\n",
    "                val-=10\n",
    "                up = 1\n",
    "            else:\n",
    "                up = 0\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "        return reverse(head.next)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        num1 = num2 = 0\n",
    "        while l1:\n",
    "            num1 = 10 * num1 + l1.val\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            num2 = 10 * num2 + l2.val\n",
    "            l2 = l2.next\n",
    "        h = ListNode()\n",
    "        cur = h\n",
    "        for c in str(num1 + num2):\n",
    "            cur.next = ListNode(int(c), None)\n",
    "            cur = cur.next\n",
    "        return h.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1_list = []\n",
    "        l2_list = []\n",
    "\n",
    "        while l1:\n",
    "            l1_list.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            l2_list.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        carry = 0\n",
    "        ans = None\n",
    "\n",
    "        while l1_list or l2_list:\n",
    "            if l1_list:\n",
    "                tmp1 = l1_list.pop()\n",
    "            else:\n",
    "                tmp1 = 0\n",
    "            \n",
    "            if l2_list:\n",
    "                tmp2 = l2_list.pop()\n",
    "            else:\n",
    "                tmp2 = 0\n",
    "\n",
    "            value = (tmp1 + tmp2 + carry) % 10\n",
    "            carry = (tmp1 + tmp2 + carry) // 10\n",
    "\n",
    "            if not ans:\n",
    "                ans = ListNode(value)\n",
    "            else:\n",
    "                head = ListNode(value)\n",
    "                head.next = ans\n",
    "                ans = head\n",
    "        \n",
    "        if carry:\n",
    "            head = ListNode(carry)\n",
    "            head.next = ans\n",
    "            ans = head\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        '''\n",
    "        # 方法一：反转列表\n",
    "        def reverse(l):\n",
    "            pre = None\n",
    "            cur = l\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        \n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        add = 0\n",
    "        while l1 or l2 or add:\n",
    "            if l1:\n",
    "                val1 = l1.val\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                val1 = 0\n",
    "            if l2:\n",
    "                val2 = l2.val\n",
    "                l2 = l2.next\n",
    "            else:\n",
    "                val2 = 0\n",
    "            val = val1 + val2 + add\n",
    "            new_node = ListNode(val%10)\n",
    "            add = val // 10\n",
    "            cur.next = new_node\n",
    "            cur = cur.next\n",
    "        return reverse(dummy.next)\n",
    "        '''\n",
    "\n",
    "        # 方法二：栈\n",
    "        stack1 = []\n",
    "        head1 = l1\n",
    "        while head1:\n",
    "            stack1.append(head1.val)\n",
    "            head1 = head1.next\n",
    "        stack2 = []\n",
    "        head2 = l2\n",
    "        while head2:\n",
    "            stack2.append(head2.val)\n",
    "            head2 = head2.next\n",
    "        \n",
    "        add = 0\n",
    "        back = None\n",
    "        while stack1 or stack2 or add:\n",
    "            if stack1:\n",
    "                val1 = stack1.pop()\n",
    "            else:\n",
    "                val1 = 0\n",
    "            if stack2:\n",
    "                val2 = stack2.pop()\n",
    "            else:\n",
    "                val2 = 0\n",
    "            val = val1 + val2 + add\n",
    "            new_node = ListNode(val%10)\n",
    "            add = val // 10\n",
    "            new_node.next = back\n",
    "            back = new_node\n",
    "        return back"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1, stack2 = [], []\n",
    "        \n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0\n",
    "\n",
    "        res_lst = []\n",
    "        while stack1 or stack2 or carry > 0:\n",
    "            if stack1 and stack2:\n",
    "                temp_val = (stack1.pop() + stack2.pop() + carry) \n",
    "            elif stack1:\n",
    "                temp_val = (stack1.pop() + carry) \n",
    "            elif stack2:\n",
    "                temp_val = (stack2.pop() + carry)\n",
    "            else:\n",
    "                temp_val = carry\n",
    "            \n",
    "            real_val = temp_val % 10\n",
    "            carry = temp_val // 10\n",
    "            res_lst.append(real_val)\n",
    "        \n",
    "        res_lst = res_lst[::-1]\n",
    "        res_node = ListNode(res_lst[0])\n",
    "        temp = res_node\n",
    "        if len(res_lst) == 1:\n",
    "            return res_node\n",
    "        \n",
    "        for val in res_lst[1:]:\n",
    "            temp.next = ListNode(val)\n",
    "            temp = temp.next\n",
    "        \n",
    "        return res_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 先反转链表，再用0002.两数相加方法解决\n",
    "        # 反转l1，l2\n",
    "        rl1 = self.reverse(l1)\n",
    "        rl2 = self.reverse(l2)\n",
    "\n",
    "        dummy_head = ListNode(-1)\n",
    "        cur = dummy_head\n",
    "        carry = 0\n",
    "        while rl1 or rl2 or carry:\n",
    "            if rl1:\n",
    "                num1 = rl1.val\n",
    "                rl1 = rl1.next\n",
    "            else:\n",
    "                num1 = 0\n",
    "            if rl2:\n",
    "                num2 = rl2.val\n",
    "                rl2 = rl2.next\n",
    "            else:\n",
    "                num2 = 0\n",
    "            sum = num1 + num2 + carry\n",
    "            carry = sum // 10\n",
    "            inplace_sum = sum % 10\n",
    "            cur.next = ListNode(inplace_sum)\n",
    "            cur = cur.next\n",
    "\n",
    "        # 将结果反转\n",
    "        ans = self.reverse(dummy_head.next)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    # 反转链表函数\n",
    "    def reverse(self, l):\n",
    "        pre = None\n",
    "        cur = l\n",
    "        while cur:\n",
    "            temp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = temp\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur//10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1, stack2 = [],[]\n",
    "        # 遍历两个链表，进行入栈操作\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                stack1.append(l1.val)\n",
    "                l1 = l1.next\n",
    "            \n",
    "            if l2:\n",
    "                stack2.append(l2.val)\n",
    "                l2 = l2.next\n",
    "        \n",
    "        # 出栈操作，并按位相加\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while stack1 and stack2:\n",
    "            n1 = stack1.pop()\n",
    "            n2 = stack2.pop()\n",
    "\n",
    "            r = n1 + n2 + carry\n",
    "\n",
    "            carry = r // 10\n",
    "            val = r % 10\n",
    "            cur_node = ListNode(val)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "        \n",
    "        while stack1:\n",
    "            n1 = stack1.pop()\n",
    "\n",
    "            r = n1 + carry\n",
    "            carry = r // 10\n",
    "            val = r % 10\n",
    "            cur_node = ListNode(val)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "        \n",
    "        while stack2:\n",
    "            n1 = stack2.pop()\n",
    "\n",
    "            r = n1 + carry\n",
    "            carry = r // 10\n",
    "            val = r % 10\n",
    "            cur_node = ListNode(val)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "        \n",
    "        if carry > 0:\n",
    "            cur_node = ListNode(carry)\n",
    "            cur_node.next = ans\n",
    "            ans = cur_node\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0,    next=None):\n",
    "    \n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1=''\n",
    "        while l1:\n",
    "            s1=s1+str(l1.val)\n",
    "            l1=l1.next\n",
    "        s2 = ''\n",
    "        while l2:\n",
    "            s2 = s2 + str(l2.val)\n",
    "            l2 = l2.next\n",
    "        l=[int(i) for i in list(str(int(s1)+int(s2)))]\n",
    "        hh=ListNode(l.pop(0),None)\n",
    "        h=hh\n",
    "        while l:\n",
    "            nd=ListNode(l.pop(0),None)\n",
    "            h.next=nd\n",
    "            h=h.next\n",
    "        return hh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1_sum = \"\"\n",
    "        l2_sum = \"\"\n",
    "        p1 = l1\n",
    "        p2 = l2\n",
    "        while p1 is not None:\n",
    "            l1_sum += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2 is not None:\n",
    "            l2_sum += str(p2.val)\n",
    "            p2 = p2.next\n",
    "\n",
    "        num1 = int(l1_sum)\n",
    "        num2 = int(l2_sum)\n",
    "        nums_sum_str = str(num1 + num2)\n",
    "        dummy = ListNode()\n",
    "        tail = dummy\n",
    "        for char in nums_sum_str:\n",
    "            node = ListNode(int(char))\n",
    "            tail.next = node\n",
    "            tail = tail.next\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                stack1.append(l1.val)\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                stack2.append(l2.val)\n",
    "                l2 = l2.next\n",
    "        cur = None\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry:\n",
    "            val1 = stack1.pop() if stack1 else 0\n",
    "            val2 = stack2.pop() if stack2 else 0\n",
    "            total = val1 + val2 + carry\n",
    "            carry = total // 10\n",
    "            temp = ListNode(total % 10)\n",
    "            if cur:\n",
    "                temp.next = cur\n",
    "                cur = temp\n",
    "            else:\n",
    "                cur = temp\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack_1 = []\n",
    "        stack_2 = []\n",
    "        while l1:\n",
    "            stack_1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        while l2:\n",
    "            stack_2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        following = None\n",
    "        carry = 0\n",
    "        while stack_1 or stack_2:\n",
    "            num_1 = stack_1.pop() if stack_1 else 0\n",
    "            num_2 = stack_2.pop() if stack_2 else 0\n",
    "            temp = (carry + num_1 + num_2) % 10\n",
    "            carry = (carry + num_1 + num_2) // 10\n",
    "            curr = ListNode(temp)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "        \n",
    "        if carry:\n",
    "            curr = ListNode(carry)\n",
    "            curr.next = following\n",
    "            following = curr\n",
    "\n",
    "        return following"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        def reverse(root):\n",
    "            if not root:\n",
    "                return root\n",
    "            pre = None\n",
    "            cur = root\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre, cur = cur, nxt\n",
    "            return pre\n",
    "\n",
    "        def _add(l1, l2, carry):\n",
    "            \n",
    "            if l1 is None and l2 is None:\n",
    "                return ListNode(carry) if carry else None\n",
    "            if l1 is None:\n",
    "                l1, l2 = l2, l1\n",
    "\n",
    "            carry += l1.val + (l2.val if l2 else 0)\n",
    "            l1.val = carry % 10\n",
    "            l1.next = _add(l1.next, l2.next if l2 else None, carry // 10)\n",
    "            return l1\n",
    "\n",
    "        rev_l1 = reverse(l1)\n",
    "        rev_l2 = reverse(l2)\n",
    "\n",
    "        rev_root = _add(rev_l1, rev_l2, 0)               \n",
    "        return reverse(rev_root)\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverList(self,head):\n",
    "        pre=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=temp\n",
    "        return pre\n",
    "    \n",
    "    def addtwoSum(self,l1,l2):\n",
    "        cur=dummy=ListNode()\n",
    "        carry=0\n",
    "        while l1 or l2 or carry:\n",
    "            if l1: carry=carry+l1.val\n",
    "            if l2: carry=carry+l2.val\n",
    "            cur.next=ListNode(carry%10)\n",
    "            carry=carry//10\n",
    "            cur=cur.next\n",
    "            if l1: l1=l1.next\n",
    "            if l2: l2=l2.next\n",
    "\n",
    "        return dummy.next\n",
    "    \n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        reverl1=self.reverList(l1)\n",
    "        reverl2=self.reverList(l2)\n",
    "        addresult=self.addtwoSum(reverl1,reverl2)\n",
    "        result=self.reverList(addresult)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "\r\n",
    "\r\n",
    "def rev(head):\r\n",
    "    cur, pre = head, None\r\n",
    "    while cur:\r\n",
    "        nxt = cur.next\r\n",
    "        cur.next = pre\r\n",
    "        pre = cur\r\n",
    "        cur = nxt\r\n",
    "    return pre\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "        l1 = rev(l1)\r\n",
    "        l2 = rev(l2)\r\n",
    "\r\n",
    "        cur = dummy = ListNode()\r\n",
    "        carry = 0\r\n",
    "        while l1 or l2 or carry:\r\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\r\n",
    "            cur.next = ListNode(val=carry % 10)\r\n",
    "            carry //= 10\r\n",
    "            cur = cur.next\r\n",
    "            if l1:\r\n",
    "                l1 = l1.next\r\n",
    "            if l2:\r\n",
    "                l2 = l2.next\r\n",
    "        return rev(dummy.next)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #Optional 可选参数\n",
    "        def decodeNode(ln: ListNode) -> str:\n",
    "            snum = \"\"\n",
    "            i = ln\n",
    "            while(i != None):\n",
    "                snum += str(i.val)\n",
    "                i = i.next\n",
    "            return snum\n",
    "\n",
    "        def encodeNode(n: int) -> ListNode:\n",
    "            sn = str(n)[::-1]\n",
    "            # print(sn)\n",
    "            lnnext = ListNode(val=int(sn[0]))\n",
    "            for i in range(1,len(sn)):\n",
    "                lnnum = ListNode(int(sn[i]),lnnext)\n",
    "                lnnext = lnnum\n",
    "            return lnnext\n",
    "\n",
    "            \n",
    "        s1 = decodeNode(l1)\n",
    "        s2 = decodeNode(l2)\n",
    "        \n",
    "        ia = int(s1) + int(s2)\n",
    "        # print(s1,s2,ia)\n",
    "        return encodeNode(ia)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(l):\n",
    "            pre = None\n",
    "            cur = l\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        L1, L2 = [], []\n",
    "        while l1:\n",
    "            L1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            L2.append(l2)\n",
    "            l2 = l2.next\n",
    "\n",
    "        up = 0\n",
    "        res = []\n",
    "        while L1 or L2 or up:\n",
    "            val = up\n",
    "            if L1:\n",
    "                val += L1.pop().val\n",
    "            if L2:\n",
    "                val += L2.pop().val\n",
    "            if val>=10:\n",
    "                val-=10\n",
    "                up = 1\n",
    "            else:\n",
    "                up = 0\n",
    "            res.append(ListNode(val))\n",
    "\n",
    "        for i in range(len(res)-1, -1, -1):\n",
    "            if i == 0:\n",
    "                res[i].next = None\n",
    "            else:\n",
    "                res[i].next = res[i-1]            \n",
    "        return res[-1]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 反转链表\n",
    "        pre=None\n",
    "        cur=head # 将当前指针指向首元结点\n",
    "        while cur:\n",
    "            nxt=cur.next\n",
    "            cur.next=pre\n",
    "            pre=cur\n",
    "            cur=nxt\n",
    "        return pre\n",
    "        \n",
    "    def resultList(self, l1: Optional[ListNode] , l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 将两个链表进行相加运算\n",
    "        p=ass=ListNode(None)\n",
    "        carry=0\n",
    "        while l1 or l2:\n",
    "            temp=(l1.val if l1 else 0)+(l2.val if l2 else 0)+carry\n",
    "            p.next=ListNode(temp%10)\n",
    "            p=p.next\n",
    "            carry=temp//10 # 取整\n",
    "            l1=l1.next if l1 else 0\n",
    "            l2=l2.next if l2 else 0\n",
    "        if carry:\n",
    "            p.next=ListNode(1)\n",
    "        return ass.next\n",
    "    \n",
    "    def addTwoNumbers(self, l1: Optional[ListNode] , l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1=self.reverseList(l1) # 将两个链表进行反转操作\n",
    "        l2=self.reverseList(l2)\n",
    "        l3=self.resultList(l1,l2)\n",
    "        return self.reverseList(l3)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _reverser(self, cur: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 双指针迭代-反转\n",
    "        # pred=sentienlle=ListNode()\n",
    "        pred = None\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=pred\n",
    "            pred=cur\n",
    "            cur=temp\n",
    "        return pred\n",
    "\n",
    "    def _addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:\n",
    "        # 递归-两数相加\n",
    "        if l1 is None and l2 is None:\n",
    "            return ListNode(carry) if carry else None\n",
    "        # 设置假定l1是最长的那个\n",
    "        if l1 is None:\n",
    "            l1,l2=l2,l1\n",
    "        carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "        l1.val = carry%10\n",
    "        l1.next = self._addTwo(l1.next, l2.next if l2 else None,carry=carry//10)\n",
    "        return l1\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self._reverser(l1)\n",
    "        l2 = self._reverser(l2)\n",
    "        l1 = self._addTwo(l1, l2)\n",
    "        return self._reverser(l1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # reverse the linked list\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        l3 = self.addTwo(l1, l2)\n",
    "        return self.reverseList(l3)\n",
    "\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        carry = 0\n",
    "        dummyHead = ListNode(0)\n",
    "        cur = dummyHead\n",
    "        while l1 or l2:\n",
    "            x = 0 if l1 == None else l1.val\n",
    "            y = 0 if l2 == None else l2.val\n",
    "            sum = 0\n",
    "            sum += (x + y + carry)\n",
    "\n",
    "            carry = sum // 10\n",
    "            sum = sum % 10\n",
    "\n",
    "            cur.next = ListNode(sum)\n",
    "            cur = cur.next\n",
    "\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        if carry != 0:\n",
    "            cur.next = ListNode(carry)\n",
    "        return dummyHead.next\n",
    "\n",
    "\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def fanzhuan(l: Optional[ListNode])-> Optional[ListNode]:\n",
    "        cur = l\n",
    "        pre = None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p1 = fanzhuan(l1)\n",
    "        p2 = fanzhuan(l2)\n",
    "        p3 = dummy = ListNode()\n",
    "        carry = 0\n",
    "        while p1 or p2 or carry:\n",
    "            if p1: carry += p1.val\n",
    "            if p2: carry += p2.val\n",
    "            p3.next = ListNode(carry % 10)  # 每个节点保存一个数位\n",
    "            carry //= 10  # 新的进位\n",
    "            p3 = p3.next  # 下一个节点\n",
    "            if p1: p1 = p1.next  # 下一个节点\n",
    "            if p2: p2 = p2.next  # 下一个节点\n",
    "\n",
    "        return fanzhuan(dummy.next)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #反转链表\n",
    "        pre1=None\n",
    "        cur1=l1\n",
    "        while cur1:\n",
    "            nxt1 = cur1.next\n",
    "            cur1.next = pre1\n",
    "            pre1 = cur1\n",
    "            cur1 = nxt1\n",
    "        #此时l1头节点pre1\n",
    "        pre2=None\n",
    "        cur2=l2\n",
    "        while cur2:\n",
    "            nxt2 = cur2.next\n",
    "            cur2.next = pre2\n",
    "            pre2 = cur2\n",
    "            cur2 = nxt2\n",
    "        #此时l2头节点pre2:\n",
    "        cur1 = pre1\n",
    "        cur2 = pre2\n",
    "        dummy = cur1\n",
    "        flag = 0\n",
    "        while cur1 and cur2:\n",
    "            cur1.val = cur1.val + cur2.val + flag\n",
    "            flag = 0\n",
    "            if cur1.val >9:\n",
    "                cur1.val -= 10\n",
    "                flag +=1\n",
    "            pre1 = cur1\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "\n",
    "        while cur1:\n",
    "            cur1.val = cur1.val + flag\n",
    "            flag = 0\n",
    "            if cur1.val >9:\n",
    "                cur1.val -= 10\n",
    "                flag +=1\n",
    "            pre1 = cur1\n",
    "            cur1 = cur1.next\n",
    "\n",
    "        while cur2:\n",
    "            cur1 = ListNode(val = 0)\n",
    "            pre1.next = cur1\n",
    "            cur1.val = cur2.val + flag\n",
    "            flag = 0\n",
    "            if cur1.val >9:\n",
    "                cur1.val -= 10\n",
    "                flag +=1\n",
    "            pre1 = cur1\n",
    "            cur2 = cur2.next\n",
    "            cur1 = cur1.next\n",
    "\n",
    "        if flag == 1:\n",
    "            cur1 = ListNode(val = 1)\n",
    "            pre1.next = cur1\n",
    "\n",
    "        pre1=None\n",
    "        cur1=dummy\n",
    "        while cur1:\n",
    "            nxt1 = cur1.next\n",
    "            cur1.next = pre1\n",
    "            pre1 = cur1\n",
    "            cur1 = nxt1\n",
    "        return pre1\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        \n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or carry != 0:\n",
    "            if s1:\n",
    "                a = s1.pop()\n",
    "            else:\n",
    "                a = 0\n",
    "            if s2:\n",
    "                b = s2.pop()\n",
    "            else:\n",
    "                b = 0\n",
    "            num = a + b + carry\n",
    "            carry = num // 10\n",
    "            cur = num % 10\n",
    "            node = ListNode(cur)\n",
    "            node.next = ans\n",
    "            ans = node\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _reverser(self, cur: Optional[ListNode], pred: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 递归-反转\n",
    "        if cur is None:\n",
    "            return pred\n",
    "        res = self._reverser(cur.next, cur)\n",
    "        cur.next = pred\n",
    "        return res\n",
    "\n",
    "    def _addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:\n",
    "        # 递归-两数相加\n",
    "        if l1 is None and l2 is None:\n",
    "            return ListNode(carry) if carry else None\n",
    "        # 设置假定l1是最长的那个\n",
    "        if l1 is None:\n",
    "            l1,l2=l2,l1\n",
    "        carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "        l1.val = carry%10\n",
    "        l1.next = self._addTwo(l1.next, l2.next if l2 else None,carry=carry//10)\n",
    "        return l1\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self._reverser(l1, None)\n",
    "        l2 = self._reverser(l2, None)\n",
    "        l1 = self._addTwo(l1, l2)\n",
    "        return self._reverser(l1, None)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "#梁佟辉方法：反转链表相加再反转链表\n",
    "# class Solution:\n",
    "#     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "#         #反转链表\n",
    "#         pre1=None\n",
    "#         cur1=l1\n",
    "#         while cur1:\n",
    "#             nxt1 = cur1.next\n",
    "#             cur1.next = pre1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = nxt1\n",
    "#         #此时l1头节点pre1\n",
    "#         pre2=None\n",
    "#         cur2=l2\n",
    "#         while cur2:\n",
    "#             nxt2 = cur2.next\n",
    "#             cur2.next = pre2\n",
    "#             pre2 = cur2\n",
    "#             cur2 = nxt2\n",
    "#         #此时l2头节点pre2:\n",
    "#         cur1 = pre1\n",
    "#         cur2 = pre2\n",
    "#         dummy = cur1\n",
    "#         flag = 0\n",
    "#         while cur1 and cur2:\n",
    "#             cur1.val = cur1.val + cur2.val + flag\n",
    "#             flag = 0\n",
    "#             if cur1.val >9:\n",
    "#                 cur1.val -= 10\n",
    "#                 flag +=1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = cur1.next\n",
    "#             cur2 = cur2.next\n",
    "\n",
    "#         while cur1:\n",
    "#             cur1.val = cur1.val + flag\n",
    "#             flag = 0\n",
    "#             if cur1.val >9:\n",
    "#                 cur1.val -= 10\n",
    "#                 flag +=1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = cur1.next\n",
    "\n",
    "#         while cur2:\n",
    "#             cur1 = ListNode(val = 0)\n",
    "#             pre1.next = cur1\n",
    "#             cur1.val = cur2.val + flag\n",
    "#             flag = 0\n",
    "#             if cur1.val >9:\n",
    "#                 cur1.val -= 10\n",
    "#                 flag +=1\n",
    "#             pre1 = cur1\n",
    "#             cur2 = cur2.next\n",
    "#             cur1 = cur1.next\n",
    "\n",
    "#         if flag == 1:\n",
    "#             cur1 = ListNode(val = 1)\n",
    "#             pre1.next = cur1\n",
    "\n",
    "#         pre1=None\n",
    "#         cur1=dummy\n",
    "#         while cur1:\n",
    "#             nxt1 = cur1.next\n",
    "#             cur1.next = pre1\n",
    "#             pre1 = cur1\n",
    "#             cur1 = nxt1\n",
    "#         return pre1\n",
    "\n",
    "#0x3f:\n",
    "class Solution:\n",
    "    # 视频讲解 https://www.bilibili.com/video/BV1sd4y1x7KN/\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = dummy = ListNode()  # 哨兵节点\n",
    "        carry = 0  # 进位\n",
    "        while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代\n",
    "            if l1: carry += l1.val  # 节点值和进位加在一起\n",
    "            if l2: carry += l2.val  # 节点值和进位加在一起\n",
    "            cur.next = ListNode(carry % 10)  # 每个节点保存一个数位\n",
    "            carry //= 10  # 新的进位\n",
    "            cur = cur.next  # 下一个节点\n",
    "            if l1: l1 = l1.next  # 下一个节点\n",
    "            if l2: l2 = l2.next  # 下一个节点\n",
    "        return dummy.next  # 哨兵节点的下一个节点就是头节点\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)  # l1 和 l2 反转后，就变成【2. 两数相加】了\n",
    "        l3 = self.addTwo(l1, l2)\n",
    "        return self.reverseList(l3)  # 计算完毕后再反转\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            total = a + b + carry\n",
    "            carry = total // 10\n",
    "            cur = total % 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        st1=[]\n",
    "        st2=[]\n",
    "        while l1:\n",
    "            st1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            st2.append(l2.val)\n",
    "            l2=l2.next\n",
    "        carry=0\n",
    "        dummy=ListNode(0)\n",
    "        while st1 or st2 or carry:\n",
    "            v1=st1.pop() if st1 else 0\n",
    "            v2=st2.pop() if st2 else 0\n",
    "            sum=v1+v2+carry\n",
    "            carry=1 if sum>=10 else 0\n",
    "            sum=sum-10 if sum>=10 else sum\n",
    "            cur=ListNode(sum)\n",
    "            cur.next=dummy.next\n",
    "            dummy.next=cur\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self,head:Optional[ListNode]):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        new_head=self.reverseList(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "        return new_head\n",
    "    \n",
    "    def addTwo(self,l1:Optional[ListNode],l2:Optional[ListNode],c=0):\n",
    "        if l1 is None and l2 is None:\n",
    "            return ListNode(c) if c else None\n",
    "        if l1 is None:\n",
    "            l1,l2=l2,l1\n",
    "        c+=l1.val+(l2.val if l2 else 0)\n",
    "        l1.val=c%10\n",
    "        l1.next=self.addTwo(l1.next,l2.next if l2 else None,c//10)\n",
    "        return l1\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1,l2=self.reverseList(l1),self.reverseList(l2)\n",
    "        l3=self.addTwo(l1,l2)\n",
    "        return self.reverseList(l3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "        s1 = \"\"\r\n",
    "        p = l1\r\n",
    "        while p:\r\n",
    "            s1 += str(p.val)\r\n",
    "            p = p.next\r\n",
    "        s2 = \"\"\r\n",
    "        p = l2\r\n",
    "        while p:\r\n",
    "            s2 += str(p.val)\r\n",
    "            p = p.next\r\n",
    "        s = str(int(s1) + int(s2))\r\n",
    "        dummy = ListNode()\r\n",
    "        p0 = dummy\r\n",
    "        for i in range(len(s)):\r\n",
    "            p = ListNode(val=int(s[i]))\r\n",
    "            p0.next = p\r\n",
    "            p0 = p\r\n",
    "        p0.next = None\r\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def _reverser(self, cur: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代-反转\n",
    "        pred,cur = None,cur\n",
    "        while cur:\n",
    "            temp=cur.next\n",
    "            cur.next=pred\n",
    "            pred=cur\n",
    "            cur=temp\n",
    "        return pred\n",
    "\n",
    "    def _addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代-两数相加\n",
    "        # sentienlle=cur=ListNode(next=l1)     # 这是错误的做法，并不是从新构造l1而是构造cur\n",
    "        sentienlle=cur=ListNode()\n",
    "        carry=0\n",
    "        while(l1 or l2 or carry):\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry%10)               # 构造cur\n",
    "            cur=cur.next\n",
    "            if l1:l1=l1.next\n",
    "            if l2:l2=l2.next\n",
    "            carry=carry//10\n",
    "        return sentienlle.next\n",
    "        \n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self._reverser(l1)\n",
    "        l2 = self._reverser(l2)\n",
    "        l1 = self._addTwo(l1, l2)\n",
    "        return self._reverser(l1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, cur: Optional[ListNode], pre: Optional[ListNode])-> Optional[ListNode]:\n",
    "        # 递归反转列表\n",
    "        if cur is None:\n",
    "            return pre\n",
    "        res = self.reverseList(cur.next, cur)\n",
    "        cur.next = pre\n",
    "        return res\n",
    "\n",
    "    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 迭代两数相加\n",
    "        carry = 0\n",
    "        cur = dummy = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next  = ListNode(carry % 10)\n",
    "            carry = carry // 10\n",
    "            cur = cur.next\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        return dummy.next\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        l1 = self.reverseList(l1, None)\n",
    "        l2 = self.reverseList(l2, None)\n",
    "        res = self.addTwo(l1, l2)\n",
    "        return self.reverseList(res, None)\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        root_node = ListNode()\n",
    "        iter_node = root_node\n",
    "        curr = 0\n",
    "        while l1 or l2 or curr:\n",
    "            if l1 is not None:\n",
    "                curr += l1.val\n",
    "                l1 = l1.next\n",
    "            if l2 is not None:\n",
    "                curr += l2.val\n",
    "                l2 = l2.next\n",
    "\n",
    "            new_node = ListNode(val=curr % 10, next=None)\n",
    "            iter_node.next = new_node\n",
    "            iter_node = new_node\n",
    "            curr = curr // 10\n",
    "        return root_node.next\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        res = ListNode((l1.val + l2.val) % 10)\n",
    "        jinwei = (int(l1.val) + int(l2.val)) // 10\n",
    "        tmp1 = l1.next\n",
    "        tmp2 = l2.next\n",
    "        tmp3 = res\n",
    "        while tmp1 != None and tmp2 != None:\n",
    "            tmp3.next = ListNode((tmp1.val + tmp2.val + jinwei) % 10)\n",
    "            jinwei = int(tmp1.val + tmp2.val + jinwei) // 10\n",
    "            tmp3 = tmp3.next\n",
    "            tmp1 = tmp1.next\n",
    "            tmp2 = tmp2.next\n",
    "        while tmp1 != None:\n",
    "            tmp3.next = ListNode((tmp1.val + jinwei) % 10)\n",
    "            jinwei = int(tmp1.val + jinwei) // 10\n",
    "            tmp3 = tmp3.next\n",
    "            tmp1 = tmp1.next\n",
    "        while tmp2 != None:\n",
    "            tmp3.next = ListNode((tmp2.val + jinwei) % 10)\n",
    "            jinwei = int(tmp2.val + jinwei) // 10\n",
    "            tmp3 = tmp3.next\n",
    "            tmp2 = tmp2.next\n",
    "        if jinwei != 0:\n",
    "            tmp3.next = ListNode(jinwei)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dummy_head = ListNode(0)\n",
    "        cur = dummy_head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            if l1:\n",
    "                carry += l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                carry += l2.val\n",
    "                l2 = l2.next\n",
    "            cur.next = ListNode(carry % 10)\n",
    "            cur = cur.next\n",
    "            carry //= 10\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        car,res,res=0,None,ListNode(0)\n",
    "        root=res\n",
    "        while l1 or l2 or car:\n",
    "            v1,v2=0,0\n",
    "            if l1:\n",
    "                v1=l1.val\n",
    "                l1=l1.next\n",
    "            \n",
    "            if l2:\n",
    "                v2=l2.val\n",
    "                l2=l2.next\n",
    "                \n",
    "            val=(v1+v2+car)%10\n",
    "            car=int((v1+v2+car)/10)\n",
    "            \n",
    "            res.next=ListNode(val)\n",
    "            res=res.next\n",
    "            \n",
    "        return root.next\n",
    "            \n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        \n",
    "        if l1 is None and l2 is None:\n",
    "            return None\n",
    "        else:\n",
    "            l1_next = None\n",
    "            l2_next = None\n",
    "            summary = 0\n",
    "            carry = 0\n",
    "            \n",
    "            if l1 is not None:\n",
    "                summary += l1.val\n",
    "                l1_next = l1.next\n",
    "            \n",
    "            if l2 is not None:\n",
    "                summary += l2.val\n",
    "                l2_next = l2.next\n",
    "            \n",
    "            carry = summary // 10\n",
    "            mod = summary % 10\n",
    "            result = ListNode(mod)\n",
    "\n",
    "            if carry != 0:\n",
    "                if l1_next is not None:\n",
    "                    l1_next.val += carry\n",
    "                    result.next = self.addTwoNumbers(l1_next, l2_next)\n",
    "                elif l2_next is not None:\n",
    "                    l2_next.val += carry\n",
    "                    result.next = self.addTwoNumbers(l1_next, l2_next)\n",
    "                elif l1_next is None and l2_next is None:\n",
    "                    result.next = ListNode(carry)\n",
    "            else:\n",
    "                    result.next = self.addTwoNumbers(l1_next, l2_next)                \n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "#     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "#         l_out = ListNode(0)\n",
    "#         l_sum = l_out\n",
    "#         while l1 or l2:\n",
    "#             if l1 == None: l1 = ListNode(0)\n",
    "#             if l2 == None: l2 = ListNode(0)\n",
    "                \n",
    "#             sum = l1.val + l2.val +l_sum.val\n",
    "#             sum_carry = sum // 10\n",
    "#             l_sum.val = sum % 10\n",
    "#             if l1.next == None and l2.next == None and sum_carry == 0:\n",
    "#                 l_sum.next = None\n",
    "#                 break\n",
    "                \n",
    "#             else: l_sum.next = ListNode(sum_carry)\n",
    "\n",
    "#             l1 = l1.next\n",
    "#             l2 = l2.next\n",
    "#             l_sum = l_sum.next\n",
    "            \n",
    "        \n",
    "#         return l_out\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l_out = ListNode(0)\n",
    "        l_sum = l_out\n",
    "        carry = 0\n",
    "        x = l1.val\n",
    "        y = l2.val\n",
    "        while l1 or l2:\n",
    "            if l1 == None: x = 0\n",
    "            else: \n",
    "                x = l1.val\n",
    "                l1 = l1.next\n",
    "            if l2 == None: y = 0\n",
    "            else: \n",
    "                y = l2.val\n",
    "                l2 = l2.next\n",
    "                      \n",
    "            sum = x + y + carry\n",
    "            \n",
    "            carry = sum // 10\n",
    "\n",
    "            l_sum.next = ListNode(sum % 10)\n",
    "            l_sum = l_sum.next\n",
    "        \n",
    "        if carry == 1:\n",
    "            l_sum.next = ListNode(1)\n",
    "               \n",
    "        return l_out.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        a,b = l1,l2\n",
    "        f1 = ListNode(a.val+b.val)\n",
    "        f2 = f1\n",
    "        while a.next or b.next:\n",
    "            if f1.val>=10:\n",
    "                f1.val =f1.val-10\n",
    "                flag = 1\n",
    "            else:\n",
    "                flag=0\n",
    "            if not a.next:\n",
    "                a.val = 0\n",
    "            else:\n",
    "                a = a.next\n",
    "            if not b.next:\n",
    "                b.val = 0\n",
    "            else:\n",
    "                b = b.next\n",
    "            f1.next =ListNode(a.val+b.val+flag)\n",
    "            print(f1.next.val)\n",
    "            f1 = f1.next\n",
    "        if f1.val>=10:\n",
    "            f1.val-=10\n",
    "            f1.next = ListNode(1)\n",
    "            \n",
    "\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':\n",
    "        num1 = 0\n",
    "        num2 = 0\n",
    "        # number1\n",
    "        node = l1\n",
    "        k = 1\n",
    "        while(node.next != None):\n",
    "            print(node.val)\n",
    "            num1 = num1 + node.val*k\n",
    "            k = k*10\n",
    "            node = node.next\n",
    "        num1 = num1 + node.val*k\n",
    "        # number2\n",
    "        node = l2\n",
    "        k = 1\n",
    "        while(node.next != None):\n",
    "            num2 = num2 + node.val*k\n",
    "            k = k*10\n",
    "            node = node.next\n",
    "        num2 = num2 + node.val*k\n",
    "        sum = num1 + num2\n",
    "        sumlist = []\n",
    "        while(sum!=0):\n",
    "            sumlist.append(sum%10)\n",
    "            sum = sum//10\n",
    "        return sumlist if(sumlist != []) else [0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        ans = ListNode(0)  #新建一个节点，初始值为0      \n",
    "        temp = ans\n",
    "        tempsum = 0\n",
    "        \n",
    "        while True:\n",
    "            if (l1 != None):\n",
    "                tempsum = l1.val + tempsum                     #l1链表节点值添加到总和里\n",
    "                l1 = l1.next                                   #指针指向下一个节点\n",
    "            if (l2 != None):\n",
    "                tempsum = tempsum + l2.val                     #l2链表节点值添加到总和里\n",
    "                l2 = l2.next                                   #指针指向下一个节点    \n",
    "            temp.val = tempsum % 10                            #取余数（满十进位），赋值当前节点值 \n",
    "            print(tempsum)\n",
    "            tempsum  = int(tempsum / 10)                       #获取进位数赋值给总和（比如tempsum为10则进1位，否则进位为0），下一次节点相加，从新的总和开始。\n",
    "            if l1 == None  and l2 == None and tempsum == 0:    #直到没有进位了，同时节点位空了，跳出循环。（这里加上tempsum==0条件是因为，最后两个节\n",
    "                break                                          #点和值可能大于10）                           \n",
    "            temp.next = ListNode(0)                            #新建下一个节点，存放和\n",
    "            temp = temp.next                                   #指针指向下一个节点\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        # 1. 处理其中一个链表为空的情况，仅需返回另外一个链表即可\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        \n",
    "        # 2. 设置两个链表指针，从链表头结点开始依次对对应的链表结点相加\n",
    "        res=ListNode(0)   # 结果链表，同样使用哑结点来进行代码简化\n",
    "        carrier=0         # 来自于上一位相加结果的进位数值\n",
    "        respos=res        # 结果链表指针\n",
    "        pos1=l1           # 链表1指针\n",
    "        pos2=l2           # 链表2指针\n",
    "\n",
    "        while pos1 or pos2 or carrier:\n",
    "            # 2.1 计算本位结果和进位\n",
    "            temp=(pos1.val if pos1 else 0)+(pos2.val if pos2 else 0)+carrier\n",
    "            print(temp)\n",
    "            value=temp%10\n",
    "            carrier=temp//10   #注意python3中的整数除法为双斜线\n",
    "            respos.next=ListNode(value)\n",
    "            \n",
    "            # 2.2 更新各个链表的指针\n",
    "            pos1=pos1.next if pos1 else pos1\n",
    "            pos2=pos2.next if pos2 else pos2\n",
    "            respos=respos.next\n",
    "\n",
    "        return res.next\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "        \n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        relist = ListNode(0)\n",
    "        tlist = relist\n",
    "        carry = 0\n",
    "        while l1 or l2:\n",
    "            n1 = l1.val if l1 else 0\n",
    "            n2 = l2.val if l2 else 0\n",
    "            s = n1 + n2 + carry\n",
    "            carry = s//10\n",
    "            print(s,carry)\n",
    "            tlist.next = ListNode(s%10)\n",
    "            tlist = tlist.next\n",
    "            \n",
    "            if l1: \n",
    "                l1 = l1.next \n",
    "            if l2:\n",
    "                l2 = l2.next \n",
    "            \n",
    "        if(carry>0):\n",
    "            tlist.next=ListNode(carry)\n",
    "        return relist.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"                   \n",
    "        #l1.val表示当前链表的值，l1.next表示链表指针指向下一个节点\n",
    "        #创建头节点\n",
    "        self.head=ListNode(0)\n",
    "        p=self.head\n",
    "        more=0\n",
    "        more1=0\n",
    "        more2=0\n",
    "        while(l1!=None and l2!=None):\n",
    "            value=l1.val+l2.val+more\n",
    "            \n",
    "            data=list(str(value))\n",
    "            \n",
    "            if(len(data)==1):\n",
    "                node=ListNode(int(data[0]))\n",
    "                print(int(data[0]),more)\n",
    "                more=0\n",
    "            else:\n",
    "                node=ListNode(int(data[1]))\n",
    "                print(int(data[1]),more)\n",
    "                more=int(data[0])\n",
    "            \n",
    "            p.next=node\n",
    "            p=p.next\n",
    "            l1=l1.next\n",
    "            l2=l2.next\n",
    "        \n",
    "        if(l1!=None and l2==None):\n",
    "            more1=more\n",
    "        if(l2!=None and l1==None):\n",
    "            more2=more\n",
    "        \n",
    "        while(l1!=None):\n",
    "            value=l1.val+more1\n",
    "            data=list(str(value))\n",
    "            #print(data)\n",
    "            if(len(data)==1):\n",
    "                node=ListNode(int(data[0]))\n",
    "                print(int(data[0]),more1)\n",
    "                more1=0\n",
    "            else:\n",
    "                node=ListNode(int(data[1]))\n",
    "                print(int(data[1]),more1)\n",
    "                more1=int(data[0])\n",
    "            #print(more1)     \n",
    "            p.next=node\n",
    "            p=p.next\n",
    "            l1=l1.next\n",
    "            more=0\n",
    "        while(l2!=None):\n",
    "            value=l2.val+more2\n",
    "            data=list(str(value))\n",
    "            #print(data)\n",
    "            if(len(data)==1):\n",
    "                node=ListNode(int(data[0]))\n",
    "                more2=0\n",
    "            else:\n",
    "                node=ListNode(int(data[1]))\n",
    "                more2=int(data[0])\n",
    "            #print(more)\n",
    "            p.next=node\n",
    "            p=p.next\n",
    "            l2=l2.next\n",
    "            more=0\n",
    "        if(more!=0):\n",
    "            node=ListNode(more)\n",
    "            p.next=node\n",
    "        if(more1!=0):\n",
    "            node=ListNode(more1)\n",
    "            p.next=node\n",
    "        if(more2!=0):\n",
    "            node=ListNode(more2)\n",
    "            p.next=node\n",
    "        p=self.head\n",
    "        p.val=p.next.val\n",
    "        p.next=p.next.next\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        head, carry = ListNode(0), 0\n",
    "        node, zero = head, ListNode(0)\n",
    "        while l1 or l2:\n",
    "            if not l1:\n",
    "                l1 = zero\n",
    "            if not l2:\n",
    "                l2 = zero\n",
    "            val = l1.val+l2.val+carry\n",
    "            print(l1.val, l2.val)\n",
    "            carry, val = divmod(val, 10)\n",
    "            node.next = ListNode(val)\n",
    "            node = node.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        if carry:\n",
    "            node.next = ListNode(carry)\n",
    "            carry = 0\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        l3=[]\n",
    "        last=0\n",
    "        while l1.next != None and l2.next != None:\n",
    "            toVal = l1.val+l2.val\n",
    "            curVal = (toVal+last)%10\n",
    "            last = (toVal+last)//10\n",
    "            print(toVal,curVal,last)\n",
    "            l3.append(curVal)\n",
    "            l1=l1.next\n",
    "            l2=l2.next\n",
    "        if l1.next == None and l2.next==None:\n",
    "            last=last+l1.val+l2.val\n",
    "        elif l1.next == None and l2.next != None:\n",
    "            last=last+l1.val\n",
    "            while l2.next != None:\n",
    "                toVal = l2.val+last\n",
    "                curVal = toVal%10\n",
    "                last = toVal//10 \n",
    "                l3.append(curVal)\n",
    "                l2=l2.next\n",
    "            last=last+l2.val\n",
    "        else:\n",
    "            last=last+l2.val\n",
    "            while l1.next != None:\n",
    "                toVal = l1.val+last\n",
    "                curVal = toVal%10\n",
    "                last = toVal//10 \n",
    "                print(toVal,curVal,last)\n",
    "                l3.append(curVal)\n",
    "                l1=l1.next\n",
    "            last=last+l1.val\n",
    "        l3.append(last%10)\n",
    "        if last//10 >=1:\n",
    "            l3.append(last//10)\n",
    "        return l3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1=s2=''\n",
    "        while True:\n",
    "            s1+=str(l1.val)\n",
    "            if l1.next==None:\n",
    "                break\n",
    "            l1=l1.next\n",
    "        while True:\n",
    "            s2+=str(l2.val)\n",
    "            if l2.next==None:\n",
    "                break\n",
    "            l2=l2.next\n",
    "        I1=int(s1[::-1])\n",
    "        I2=int(s2[::-1])\n",
    "        I=I1+I2\n",
    "        S=str(I)[::-1]\n",
    "        res=ListNode(int(S[0]))\n",
    "        res1=res\n",
    "        for x in S[1::]:\n",
    "                     res.next=ListNode(int(x))\n",
    "                     res=res.next\n",
    "        return res1\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "def panduan(x):\n",
    "        if x==None:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "\n",
    "def panduan_val(x):\n",
    "        if x==None:\n",
    "            return 0\n",
    "        else:\n",
    "            return x.val\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        lsum_hand =ListNode(0)\n",
    "        lsum =lsum_hand\n",
    "        l1_now =l1\n",
    "        l2_now =l2\n",
    "#hand\n",
    "        lsum_jinyi =(panduan_val(l1_now)+panduan_val(l2_now))//10\n",
    "        lsum.val=(panduan_val(l1_now)+panduan_val(l2_now))%10\n",
    "        l1_now=l1_now.next if (l1_now!=None and l1_now.next!=None) else None \n",
    "        l2_now=l2_now.next if (l2_now!=None and l2_now.next!=None) else None\n",
    " #others\n",
    "        while(panduan(l1_now) or panduan(l2_now) or lsum_jinyi==1):\n",
    "            lsum.next=ListNode(0)\n",
    "            lsum=lsum.next\n",
    "            lsum.val = lsum_jinyi\n",
    "            lsum.val += panduan_val(l1_now)+panduan_val(l2_now)\n",
    "            lsum_jinyi = lsum.val//10\n",
    "            lsum.val = lsum.val%10\n",
    "            l1_now=l1_now.next if (l1_now!=None and l1_now.next!=None) else None \n",
    "            l2_now=l2_now.next if (l2_now!=None and l2_now.next!=None) else None\n",
    "        return lsum_hand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1 and l2: return l2\n",
    "        if not l2 and l1: return l1\n",
    "        if not (l1 and l2): return \n",
    "        L1,L2 = 0,0\n",
    "        m,n = 0,0\n",
    "        # 计算两链表长度并获得两链表的值\n",
    "        tmp1,tmp2 = l1,l2 \n",
    "        while tmp1:\n",
    "            m += 1\n",
    "            tmp1 = tmp1.next\n",
    "        while tmp2:\n",
    "            n += 1\n",
    "            tmp2 = tmp2.next\n",
    "        for i in range(m):\n",
    "            L1 += l1.val*(10**i)\n",
    "            l1 = l1.next\n",
    "        for j in range(n):\n",
    "            L2 += l2.val*(10**j)\n",
    "            l2 = l2.next\n",
    "        # 两链表值家和并生成list\n",
    "        val = int(L1) + int(L2)\n",
    "        tmp = list(str(val))\n",
    "        # list转化成链表，生成链表的步骤如下\n",
    "        node = ListNode(None)\n",
    "        tmp_node = ListNode(None)\n",
    "        while tmp:\n",
    "            if tmp_node.val is None:\n",
    "                tmp_node = ListNode(int(tmp.pop()))\n",
    "                node.next = tmp_node\n",
    "            else:\n",
    "                tmp_node.next = ListNode(int(tmp.pop()))\n",
    "                tmp_node = tmp_node.next\n",
    "        return node.next\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l = ListNode(0)\n",
    "        lres = l\n",
    "        carry = 0\n",
    "\n",
    "        while l1 or l2:\n",
    "            x = l1.val if l1 else 0\n",
    "            y = l2.val if l2 else 0\n",
    "            ds = x + y + carry\n",
    "            carry = ds // 10\n",
    "            ds = ds - carry * 10\n",
    "            lres.next = ListNode(ds)\n",
    "            lres = lres.next\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        if carry > 0:\n",
    "            lres.next = ListNode(carry)\n",
    "        \n",
    "        return l.next\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    " \n",
    "class Solution(object):\n",
    "    \n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        if l2 is None:\n",
    "            return l1\n",
    " \n",
    "        tmp = ListNode(0)\n",
    "        res = tmp\n",
    "        flag = 0\n",
    "        while l1 or l2:\n",
    "            tmpsum = 0\n",
    "            if l1:\n",
    "                tmpsum = l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                tmpsum += l2.val\n",
    "                l2 = l2.next\n",
    "            tmpres = ((tmpsum + flag) % 10)\n",
    "            flag = ((tmpsum + flag) // 10)\n",
    "            res.next = ListNode(tmpres)\n",
    "            res = res.next\n",
    "        if flag:\n",
    "            res.next = ListNode(1)\n",
    "        res = tmp.next\n",
    "        del tmp\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        ret = ListNode(-1)\n",
    "        ret_c  = ret\n",
    "        c=0\n",
    "        while l1 or l2:\n",
    "            if l1 and l2:\n",
    "                val = l1.val+l2.val+c\n",
    "            if not l1:\n",
    "                val = l2.val+c\n",
    "            if not l2:\n",
    "                 val = l1.val+c\n",
    "            if val<10:\n",
    "                node = ListNode(val)\n",
    "                c=0\n",
    "            else:\n",
    "                c = 1\n",
    "                node = ListNode(val-10)\n",
    "            ret.next =node\n",
    "            ret = node\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        if c==1:\n",
    "            node = ListNode(1)\n",
    "            ret.next =node\n",
    "            ret = node            \n",
    "        return ret_c.next\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res = ListNode()\n",
    "        temp = res\n",
    "        f = 0\n",
    "        while l1 or l2:           \n",
    "            v1 = l1.val if l1 else 0\n",
    "            v2 = l2.val if l2 else 0\n",
    "            temp.val = v1 + v2 + f\n",
    "            if temp.val >= 10:\n",
    "                temp.val -= 10\n",
    "                f = 1\n",
    "            else:\n",
    "                f = 0\n",
    "            if (l1 and l1.next) or (l2 and l2.next):\n",
    "                temp.next = ListNode()\n",
    "                temp = temp.next\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        if f == 1:\n",
    "            temp.next = ListNode(1)\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        p = l1\n",
    "        res1 = []\n",
    "        while p:\n",
    "            res1.append(p.val)\n",
    "            p = p.next\n",
    "        res1.reverse()\n",
    "        q = l2\n",
    "        res2 = []\n",
    "        while q:\n",
    "            res2.append(q.val)\n",
    "            q = q.next\n",
    "        res2.reverse()\n",
    "\n",
    "        first = 0\n",
    "        for i in range(len(res1)):\n",
    "            first = first * 10 + res1[i]\n",
    "\n",
    "        second = 0\n",
    "        for i in range(len(res2)):\n",
    "            second = second * 10 + res2[i]\n",
    "\n",
    "        summ = first + second  # 807\n",
    "        if summ == 0:\n",
    "            return ListNode(0)\n",
    "        l3 = ListNode(0)\n",
    "        m = l3\n",
    "        while summ:   # 7 - 0 - 8\n",
    "            cnt = summ % 10\n",
    "            newnode = ListNode(cnt)\n",
    "            m.next = newnode\n",
    "            m = newnode\n",
    "            summ //= 10\n",
    "        return l3.next\n",
    "        # sum1 = 0\n",
    "        # sum2 = 0\n",
    "        # count = 0\n",
    "\n",
    "        # while(l1 != None):\n",
    "        #     x = l1.val\n",
    "        #     sum1 += x * 10**(count)\n",
    "        #     count += 1\n",
    "        #     l1 = l1.next\n",
    "\n",
    "        # count = 0\n",
    "        # while (l2 != None):\n",
    "        #     x = l2.val\n",
    "        #     sum2 += x * 10**(count)\n",
    "        #     count += 1\n",
    "        #     l2 = l2.next\n",
    "\n",
    "        # sum = sum1 + sum2\n",
    "\n",
    "        # d = sum % 10\n",
    "        # l3 = ListNode(d)\n",
    "        # sum = sum // 10\n",
    "        # a = l3\n",
    "        # while (sum != 0):\n",
    "        #     d = sum % 10\n",
    "        #     newNode = ListNode(d)\n",
    "        #     a.next = newNode\n",
    "        #     a = newNode\n",
    "        #     sum = sum // 10\n",
    "\n",
    "        # return l3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(l1.val + l2.val)\n",
    "        if head.val >= 10:\n",
    "            head.next = ListNode(1)\n",
    "            head.val -= 10 \n",
    "        current = head\n",
    "        while l1.next or l2.next:\n",
    "            if l1.next is None:\n",
    "                l2 = l2.next\n",
    "                if current.next is None:\n",
    "                    current.next = ListNode(l2.val)\n",
    "                else:\n",
    "                    current.next.val += (l2.val) \n",
    "                \n",
    "            elif l2.next is None:\n",
    "                l1 = l1.next\n",
    "                if current.next is None:\n",
    "                    current.next = ListNode(l1.val)\n",
    "                else:\n",
    "                    current.next.val += (l1.val) \n",
    "            else:\n",
    "                l1 = l1.next\n",
    "                l2 = l2.next\n",
    "                if current.next is None:\n",
    "                    current.next = ListNode(l1.val + l2.val)\n",
    "                else:\n",
    "                    current.next.val += l1.val + l2.val\n",
    "                \n",
    "            current = current.next\n",
    "            if current.val >= 10:\n",
    "                current.next = ListNode(1)\n",
    "                current.val -= 10 \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1) #虚拟头节点\n",
    "        cur = dummy #pointer to dummy (开始先对准dummy,结束直接输出dummy.next)\n",
    "        t = 0 #进位\n",
    "        while (l1 or l2 or t):\n",
    "            if l1:\n",
    "                t+= l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                t+=l2.val\n",
    "                l2 = l2.next\n",
    "            cur.next = ListNode(t%10)\n",
    "            #记得挪cur\n",
    "            cur = cur.next\n",
    "            t = t//10\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        carry = 0\n",
    "        head = None\n",
    "        while( l1 or  l2):\n",
    "            n1, n2 = 0, 0\n",
    "            if (l1):\n",
    "                n1 = l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                n2 = l2.val\n",
    "                l2 = l2.next\n",
    "            sum = n1 + n2 + carry\n",
    "            sum, carry = sum%10, int(sum/10)\n",
    "            print(sum, carry)\n",
    "            if head is None:\n",
    "                head = ListNode(sum)\n",
    "                tail = head\n",
    "            else:\n",
    "                tail.next = ListNode(sum)\n",
    "                tail = tail.next\n",
    "        if carry > 0:\n",
    "            tail.next = ListNode(carry)\n",
    "        return head\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        # 这个可以直接按照加法的进位思想\n",
    "        ans = p = ListNode(0)\n",
    "        s= 0\n",
    "        while l1 or l2 or s:\n",
    "            s += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            p.next = ListNode(s%10)\n",
    "            p = p.next\n",
    "            s = s//10\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return ans.next\n",
    "\n",
    "\n",
    "        # a = l1\n",
    "        # b= l2\n",
    "        # sum1 = 0\n",
    "        # sum2 = 0\n",
    "        # while a:\n",
    "        #     sum1 = a.val+sum1\n",
    "        #     a = a.next\n",
    "        # while b:\n",
    "        #     sum2 = b.val+sum2\n",
    "        #     b = b.next\n",
    "        # num = sum1 + sum2\n",
    "        # listsum = ListNode(0)\n",
    "        # listsumfor = listsum\n",
    "        # array = []\n",
    "        # while True:\n",
    "        #     array.append(num%10)\n",
    "        #     num = num//10\n",
    "        #     if num<10:\n",
    "        #         array.append(num)\n",
    "        #         break\n",
    "        # L = len(array)\n",
    "        # for i in range(1,L):\n",
    "        #     listsum.next= ListNode(array[L-i])\n",
    "        #     listsum = listsum.next\n",
    "        # return listsumfor.next\n",
    "   \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        i =0\n",
    "        x=0\n",
    "        while l1:\n",
    "            temp = l1.val\n",
    "            l1 = l1.next\n",
    "            x = x + temp*pow(10,i)\n",
    "            i = i + 1\n",
    "            \n",
    "        i=0\n",
    "        y=0\n",
    "        while l2:\n",
    "            temp = l2.val\n",
    "            l2 = l2.next\n",
    "            y = y + temp*pow(10,i)\n",
    "            i = i + 1\n",
    "        z = x + y\n",
    "        str_sum = str(z)\n",
    "        head = ListNode(None)\n",
    "        temp_node =ListNode(None)\n",
    "        for ch in str_sum[::-1]:\n",
    "            print(ch)\n",
    "            if not head.val:\n",
    "                head.val = ch\n",
    "                temp = head\n",
    "            else:\n",
    "                temp.next = ListNode(ch)\n",
    "                temp = temp.next\n",
    "        return head\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res = p = ListNode(None)\n",
    "        s = 0\n",
    "\n",
    "        while l1 or l2 or s != 0:\n",
    "            s += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            p.next = ListNode(s % 10)\n",
    "            p = p.next\n",
    "\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "\n",
    "            s //= 10\n",
    "        return res.next\n",
    "        # \"\"\"\n",
    "        # 方法2解题思路:\n",
    "        # 通过哑节点连接两节点相加之和, 再将结果连接\n",
    "        # \"\"\"\n",
    "        # # 创建哑节点\n",
    "        # res = p = ListNode(0)\n",
    "        # # 节点相加之和\n",
    "        # s = 0\n",
    "\n",
    "        # # 循环条件: l1没遍历完或者l2没遍历完或者 `s // 10` 之后还有进位\n",
    "        # while l1 or l2 or s != 0:\n",
    "        #     # 节点相加\n",
    "        #     s += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "        #     # 将哑变量连接新两数相加之后取余节点 (两数相加可能会>=10)\n",
    "        #     p.next = ListNode(s % 10)\n",
    "        #     # 指针指向当前的新节点\n",
    "        #     p = p.next\n",
    "\n",
    "        #     # 将l1和l2指针往后移动, 直到None\n",
    "        #     if l1:\n",
    "        #         l1 = l1.next\n",
    "\n",
    "        #     if l2:\n",
    "        #         l2 = l2.next\n",
    "\n",
    "        #     # 由于节点保存的是余数, 当两数相加>=10会有进位, 因此s需要除10取整, 用到后面一项相加\n",
    "        #     s //= 10\n",
    "        # # 返回哑变量后面的所有节点\n",
    "        # return res.next\n",
    "    #     \"\"\"\n",
    "    #     方法1解题思路:\n",
    "    #     由于数字是逆序存储于, 因此可以通过 `l.val * (10 ** digit)` 来获得正向的值\n",
    "    #     将两值相加后转为 `str` 类型后再遍历存储至节点\n",
    "    #     \"\"\"\n",
    "        \n",
    "    #     # 正向相加结果\n",
    "    #     forwardRes = str(self.getForwardRes(l1) + self.getForwardRes(l2))\n",
    "    #     # 结果倒转\n",
    "    #     backwardRes = forwardRes[::-1]\n",
    "        \n",
    "    #     n = len(backwardRes)\n",
    "    #     # 存储结果\n",
    "    #     res = [0] * n\n",
    "        \n",
    "    #     # 存储节点\n",
    "    #     for i in range(n):\n",
    "    #         res[i] = ListNode(int(backwardRes[i]))\n",
    "        \n",
    "    #     # 连接链表\n",
    "    #     for i in range(n-1):\n",
    "    #         res[i].next = res[i+1]\n",
    "        \n",
    "    #     return res[0]\n",
    "    # def getForwardRes(self, l):\n",
    "    #     \"\"\"\n",
    "    #     方法1的辅助函数, 用于获得正向链表节点结果\n",
    "    #     \"\"\"\n",
    "    #     # 结果值保存\n",
    "    #     res = 0\n",
    "    #     # 位数\n",
    "    #     digit = 0\n",
    "\n",
    "    #     # 遍历链表计算正向结果\n",
    "    #     while True:\n",
    "    #         res += (l.val) * (10 ** digit)\n",
    "    #         digit += 1\n",
    "    #         l = l.next\n",
    "    #         if not l:\n",
    "    #             break\n",
    "\n",
    "    #     return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        list1,list2 = [],[]\n",
    "        dummy_head = cur = ListNode()\n",
    "        while l1:\n",
    "            list1.insert(0,str(l1.val))\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            list2.insert(0,str(l2.val))\n",
    "            l2 = l2.next\n",
    "        addNum = int(''.join(list1))+int(''.join(list2))\n",
    "        addNum = list(str(addNum))\n",
    "        for i in range(len(addNum)):\n",
    "            addNum[i] = int(addNum[i])\n",
    "        for i in reversed(addNum):\n",
    "            node = ListNode(i)\n",
    "            cur.next = node\n",
    "            cur = cur.next\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        if not l1:\n",
    "            return l2\n",
    "        elif not l2:\n",
    "            return l1\n",
    "        sum = l1.val+l2.val\n",
    "        if sum > 9:\n",
    "            return ListNode(sum-10, self.addTwoNumbers(ListNode(1, None), self.addTwoNumbers(l1.next, l2.next)))\n",
    "        else:\n",
    "            return ListNode(sum, self.addTwoNumbers(l1.next, l2.next))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        len1=0\n",
    "        len2=0\n",
    "        l3=l1\n",
    "        while l3 is not None:\n",
    "            len1+=1\n",
    "            l3=l3.next\n",
    "        l3=l2   \n",
    "        while l3 is not None:\n",
    "            len2+=1\n",
    "            l3=l3.next\n",
    "        if len1>=len2:\n",
    "            l3=l1\n",
    "            flag=0\n",
    "            while l3 is not None:\n",
    "                if l2 is not None:\n",
    "                    l3.val=l2.val+l3.val+flag\n",
    "                else:\n",
    "                    l3.val+=flag\n",
    "                if l3.val>=10:\n",
    "                    l3.val-=10\n",
    "                    flag=1\n",
    "                    if l3.next==None:\n",
    "                        node=ListNode(len1)\n",
    "                        node.val=0\n",
    "                        l3.next=node\n",
    "                else:\n",
    "                    flag=0\n",
    "                l3=l3.next\n",
    "                if l2 is not None:\n",
    "                    l2=l2.next\n",
    "                \n",
    "                \n",
    "        else:\n",
    "            l3=l2\n",
    "            flag=0\n",
    "            while l3 is not None:\n",
    "                if l1 is not None:\n",
    "                    l3.val=l1.val+l3.val+flag\n",
    "                else:\n",
    "                    l3.val+=flag\n",
    "                if l3.val>=10:\n",
    "                    l3.val-=10\n",
    "                    flag=1\n",
    "                    if l3.next==None:\n",
    "                        node=ListNode(len2)\n",
    "                        node.val=0\n",
    "                        l3.next=node\n",
    "                else:\n",
    "                    flag=0\n",
    "                l3=l3.next\n",
    "                if l1 is not None:\n",
    "                    l1=l1.next\n",
    "\n",
    "        if len1>=len2:\n",
    "            return l1\n",
    "        else:\n",
    "            return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head = ListNode()\n",
    "        head.val = l1.val + l2.val\n",
    "        carry = 1 if head.val > 9 else 0\n",
    "        head.val = head.val % 10\n",
    "        l1 = l1.next\n",
    "        l2 = l2.next\n",
    "        node = head\n",
    "\n",
    "        while l1 or l2:\n",
    "            l1n = l1.val if l1 is not None else 0\n",
    "            l2n = l2.val if l2 is not None else 0\n",
    "            node.next = ListNode()\n",
    "            node = node.next\n",
    "            node.val = l1n + l2n + carry\n",
    "            print(str(carry) + \" \" + str(node.val))\n",
    "            carry = 1 if node.val > 9 else 0\n",
    "            node.val = node.val % 10\n",
    "            l1 = l1.next if l1 is not None else None\n",
    "            l2 = l2.next if l2 is not None else None\n",
    "        if carry:\n",
    "            node.next = ListNode()\n",
    "            node = node.next\n",
    "            node.val = 1\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans = ListNode()\n",
    "        cur = ans\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry, val = divmod(s, 10)\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return ans.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans_head = ListNode()\n",
    "        node1 = ans_head\n",
    "        flag = 0\n",
    "        while l1 != None or l2 != None:\n",
    "            if l1 == None:\n",
    "                node2 = ListNode((l2.val + flag) % 10)\n",
    "                flag = int((l2.val + flag) / 10)\n",
    "                l2 = l2.next\n",
    "            elif l2 == None:\n",
    "                node2 = ListNode((l1.val + flag) % 10)\n",
    "                flag = int((l1.val + flag) / 10)\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                node2 = ListNode((l1.val + l2.val + flag) % 10)\n",
    "                flag = int((l1.val + l2.val + flag) / 10)\n",
    "                l1 = l1.next\n",
    "                l2 = l2.next\n",
    "            node1.next = node2\n",
    "            node1 = node2\n",
    "        if flag:\n",
    "            node1.next = ListNode(1)\n",
    "        return ans_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        \n",
    "        carry = 0\n",
    "        preHead = ListNode(0)\n",
    "        curr = preHead\n",
    "\n",
    "        while l1 or l2 or carry:\n",
    "            val1 = l1.val if l1 else 0\n",
    "            val2 = l2.val if l2 else 0\n",
    "            carry, out = divmod(val1 + val2 + carry, 10)\n",
    "\n",
    "            curr.next = ListNode(out)\n",
    "            curr = curr.next\n",
    "\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return preHead.next\n",
    "        # carry = 0\n",
    "        # preHead = ListNode(0)\n",
    "        # current = preHead\n",
    "\n",
    "        # while l1 or l2 or carry:\n",
    "        #     val1 = l1.val if l1 else 0\n",
    "        #     val2 = l2.val if l2 else 0\n",
    "        #     carry, out = divmod(val1 + val2 + carry, 10)\n",
    "            \n",
    "        #     current.next = ListNode(out)\n",
    "        #     current = current.next\n",
    "\n",
    "        #     l1 = l1.next if l1 else None\n",
    "        #     l2 = l2.next if l2 else None\n",
    "\n",
    "        # return preHead.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        return self.dfs(l1, l2, 0)\n",
    "    def dfs(self, l1, l2, carry):\n",
    "        if not l1 and not l2 and not carry:\n",
    "            return None\n",
    "        cur = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "        node = ListNode(cur % 10)\n",
    "        node.next = self.dfs(l1.next if l1 else None, l2.next if l2 else None, cur // 10)\n",
    "        return node"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
